package _stack_queue

import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 * https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
 * https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
 *
 * 1047. 删除字符串中的所有相邻重复项
 *
 * 输入："abbaca"
 * 输出："ca"
 */
class leetcode_1047 {
    @Test
    fun test_1() {
        Assert.assertEquals("ca", removeDuplicates("abbaca"))
        val string:String = "1";
        string.toInt()
        val list: LinkedList<Int> = LinkedList<Int>();
        list.pop()
    }

    //    fun removeDuplicates(s: String): String {
//        /**
//        string ->char array
//        stack
//        loop (1 to n){
//        if(stack empty){
//        push to stack
//        }
//        else{
//        if(top  == current){
//        pop stack
//        }else{
//        push to stack
//        }
//        }
//        }
//        stack => string
//        return string
//         */
//
//        // T - N
//        // S - N
//        val array: CharArray = s.toCharArray()
//        val stack: LinkedList<Char> = LinkedList<Char>()
//        for (ch in array) {
//            if (stack.isEmpty()) {
//                stack.push(ch)
//            } else {
//                val top: Char = stack.peek()
//                if (top == ch) {
//                    stack.pop()
//                } else {
//                    stack.push(ch)
//                }
//            }
//        }
//        if (stack.isEmpty()) {
//            return ""
//        }
//        var r: String = ""
//        val size = stack.size
//        for (i in 1..size) {
//            r = stack.pop() + r
//        }
//        return r
//    }
    fun removeDuplicates(s: String): String {
        /**
        string ->char array
        stack
        loop (1 to n){
        if(stack empty){
        push to stack
        }
        else{
        if(top  == current){
        pop stack
        }else{
        push to stack
        }
        }
        }
        stack => string
        return string
         */
        // T - N
        // S - 1
        val array: CharArray = s.toCharArray()
        val builder: StringBuilder = StringBuilder()
        for (ch in array) {
            if (builder.isEmpty()) {
                builder.append(ch)
            } else {
                val last: Char = builder.last()
                if (last == ch) {
                    builder.deleteCharAt(builder.length - 1)
                } else {
                    builder.append(ch)
                }
            }
        }
        return builder.toString()
    }
}